Software simulators have long been used to verify the correct behavior of electronic circuit designs. As a result of Moore's Law, IC design size and complexity have continuously outpaced the capabilities to perform the desired simulations. Using current methods, it can take an impractical amount of time to perform desired simulations of large circuit designs, especially when including the detailed timing information needed for a comprehensive simulation. The more thorough the simulations, the better the chance the new IC device will succeed in manufacturing, thus the industry has a constant dilemma of how much time to spend simulating versus time-to-market considerations.
IC designers often employ hierarchical design techniques to determine the appropriate selection and interconnection of logic and/or memory devices which enable the IC to perform a desired function. These techniques involve describing the IC's functionality at various levels of abstraction, ranging from the most general function performed by the IC to the precise functions performed by each logic and/or memory element on the device. Encoding the design in a hardware description language (HDL) such as Verilog or VHDL is the usual design entry technique used to specify modern IC's. HDLs represent electronic operations as a sequence of statements in software coding. At this high level of abstraction the circuit design is represented by its “netlist,” which is “a textual file representing an ASIC design as a set of library-specific cells along with their interconnections” (EDA Consortium Glossary). It is possible to determine the functionality of the circuit design netlist as it exists in software, using such tools as behavioral simulators and static timing verifiers, but it may not be possible at this stage to include the detailed real-world models of the targeted integrated circuit manufacturing process.
The next stage in the design process is logic synthesis, in which design software takes the HDL description of the circuit design and creates the actual electronic functions (“gates” or “cells”) which are to be fabricated on the integrated circuit. During synthesis the design is “targeted” at a given integrated circuit manufacturing process, by incorporating timing and other detailed information contained in standard cell libraries that characterize the intended silicon manufacturing process technology. A cell library is a database containing detailed specifications of the characteristics of each logical component available for use in a given IC fabrication process, and thus to the designer. Synthesis and incorporation of timing data cause a large increase in the size of the data representing the circuit design, compared to the pre-synthesis netlist, which causes the simulation run-time to greatly increase. With modern large designs, this can result in simulation run-times of days and weeks, creating a demand for methods of speeding up simulation. The synthesis-simulation steps are performed repeatedly: as simulation detects errors in functionality or timing, the circuit design must be corrected and re-synthesized, and re-simulated, iteratively. The result is a logic design database which completely specifies the logical and functional relationships among the components of the design, and is used to perform placement and routing (layout) of the design's components on the integrated circuit chip.
Placement and routing determines where the actual devices are placed on the integrated circuit, and how the electrical connections are made. These decisions determine how the integrated circuit will actually perform once fabricated, especially the timing performance, making it desirable to extract the timing information from the physical design and perform post-layout simulations with timing. A primary motivation for the invention is to allow these simulations to be performed in a much shorter period of time than is available with current methods of simulation in software.
“Partitioning” may be described as a process whereby a circuit design is decomposed into smaller subcircuits, such that the subcircuits are electrically equivalent to the design being partitioned. “Electrically equivalent” means the simulation output results from running the entire circuit on a single computer (processor) are the same as running the partition subsets on individual (networked) computers, i.e., simulation-invariant. Such decomposition into subsets is called a partition of the design. The purpose of creating a partition is to permit the simulation task to be shared among two or more computers, thereby accomplishing simulation computations in less time than would be required if the entire simulation task were to be performed on a single computer.
Current methods of partitioning a large circuit design require substantial manual effort by skilled circuit designers, are generally incapable of delivering meaningful simulation speed ups, or are methods that place severe limitations on the nature of the input design. A problem inherent in simulating a design as a partition of subsets on many networked computers is the communications “overhead” that exists. Each subset needs to communicate with every other subset: for the “next” simulation step to start, each subset needs to receive its new inputs and transmit its current outputs to the other subsets.
A common method of partitioning is to divide the input design into functional blocks (“partitioning along functional boundaries”). This is often not difficult to do, but may not result in a partition that is suitable for simulation: depending on the design, the block sizes may vary by a large factor and may need further partitioning, and the communications between blocks may become extremely time consuming, i.e., communications “blow-up.”
For circuit designs with multiple clocks, a common method is to partition the circuit along its clock boundaries, as referenced in Khalil et al., U.S. Pat. No. 7,039,887; Baumgartner, U.S. Pat. No. 6,567,962; and Ruediger, U.S. Pat. No. 6,523,155. A complex circuit may have a single clock, in which case this method may not be applicable. Also, this method may not produce the desired number or type of partitions, or it may produce partitions not suitable for simulation, e.g., having too much communications overhead to be effective.
Another common method is partitioning along hierarchical boundaries is described in Zhou el al., U.S. Pat. No. 6,807,520; and Gutwin et al., U.S. Pat. No. 6,588,000; and conceptually illustrated in FIG. 1. Partitioning along hierarchical boundaries generally will not produce a desirable partition for the purposes of simulation, especially cell level simulation with timing included.
Many patents describe methods of partitioning circuits described at a high level of abstraction, e.g., as state machines for formal verification in Baumgartner, U.S. Pat. No. 6,553,514; at RTL level as described in Johannsen, U.S. Pat. No. 6,728,939; or as Boolean decision diagrams described in Jain et al., U.S. Pat. No. 7,028,278. These abstract representations cannot utilize the “real-world” timing data provided by the cell library of the target fabrication process, and the timing information derived after placement and routing, and are thus not suitable for dynamic simulation.
Some methods of partitioning are used for static analysis and/or functional verification, as referenced in Chopra et al., U.S. Pat. No. 7,047,510; Wever et al., U.S. Pat. No. 7,047,162; Jain et al., U.S. Pat. No. 7,028,278; and McGaughy, U.S. Pat. No. 7,024,652. In a static analysis the timing information is excluded, unlike the current invention.
Some methods of partitioning are optimized for such purposes as fault simulation and automatic test program generation (ATPG), as in Carpenter et al., U.S. Pat. No. 5,862,149. These methods may not be applicable when dynamic timing simulation is desired. The high level of abstraction in each case again disallows incorporation of timing data from the circuit library elements (cells) and the timing information measured after circuit layout.
Several patents describe methods of partitioning digital circuits at the transistor level, for the purposes of simulation, e.g., Khaira et al., U.S. Pat. No. 7,171,347 (transistor level); Shah, U.S. Patent Application Publication No. 20050273298; and Wei, U.S. Pat. No. 6,112,022, which operates on a SPICE netlist.
Existing methods do not apparently offer a general method for partitioning, particularly when timing data is to be included. This may preclude taking full advantage of existing design tools and techniques (e.g., cell level simulation with timing data), leading to insufficient simulation which causes expensive redesigns of new IC products.